package com.lijing.BackTracing2;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @Description 给定⼀个⽆重复元素的数组 candidates 和⼀个⽬标数 target
 * 找出 candidates 中所有可以使数字和为target 的组合
 * @title: Combination4
 * @Author LiJing
 * @Date: 2021/4/55:20 下午
 * @Version 1.0
 */
public class Combination4 {
    static List<LinkedList<Integer>> result = new ArrayList<>();
    static LinkedList<Integer> path = new LinkedList<>();
    static int pathSum = 0;
    public static void main(String[] args) {
        int[] candidates = {2,3,5};
        int target = 8;
        backTrack(0,candidates,target,pathSum);
        System.out.println(result);
    }

    /**
     * 回溯方法
     * @param startIndex 如果是一个集合求组合，就需要startIndex，如果是多个集合求组合，各集合间互不影响就不用startIndex
     * @param candidates candidates
     * @param target target
     * @param pathSum 记录临时结果path的和
     */
    public static void backTrack(int startIndex, int[] candidates, int target, int pathSum){
        if (pathSum > target){
            return;
        }
        if (pathSum == target){
            result.add(new LinkedList<>(path));
            return;
        }
        for (int i = startIndex; i < candidates.length && pathSum+candidates[i] <= target; i++) {
            //处理当前节点
            pathSum += candidates[i];
            path.addLast(candidates[i]);
            //递归，index使用i而不是i+1，意味着可以重复使用当前元素
            backTrack(i,candidates,target,pathSum);
            //回溯，取消当前操作
            pathSum -= candidates[i];
            path.removeLast();

        }
    }
}
